package com.test.daily.leetcode.y2022.m06.day0610.v03;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/10 下午 03:50
 * @version: 1.0
 */
public class Solution {

    public static int coins(int[] arr, int aim) {
        return process(arr, aim, 0);
    }

    public static int process(int[] arr, int rest, int index) {
        if (rest < 0) {
            return 0;
        }
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        return process(arr, rest, index + 1) + process(arr, rest - arr[index], index + 1);
    }

    public static int dp(int[] arr, int aim) {
        if (aim == 0) {
            return 1;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][aim] = 1;
        for (int i = N-1; i >=0 ; i--) {
            for(int rest = 0; rest <= aim; rest++){
                dp[i][rest] = dp[i+1][rest] + (rest-arr[i] >= 0 ? dp[i+1][rest-arr[i]]: 0);
            }
        }
        return dp[0][aim];
    }
}
